package string;



import java.util.*;

/**
 * @author justnow
 * Created on 2020-10-12
 * Description
 */
public class Leetcode03 {

    public static void main(String[] args) {
        String test1 = "abcabcbb";
        String mostLength = getMostLength2(test1);
        System.out.println(mostLength);
    }
    /**
     * 方法一，要求返回最长的不重复的字符串，如果有多个，返回第一个
     * @param s
     * @return
     */
    public static String getMostLength(String s) {
        if (s == null || s.length() <= 0) {
            return s;
        }
        int length= s.length();
        HashSet<Character> set = new HashSet<>();
        List<String> list = new ArrayList<>();
        int left = 0;// 表示不重复字符串的左边的起点
        int max = 0;
        char[] array = s.toCharArray();
        for (int i = 0; i < length; i++) {
            //1. 如果下标i处的元素存在的话，那么直接将其从set集合中剔除
            while (left < length && set.contains(array[i])) {
                // 2. 每剔除一个，left加1，表示不重复的字符字符串的左边的
                left++;
                set.remove(s.charAt(i));
            }
            //3. 集合中每添加元素，就求一个最大的值
            set.add(array[i]);
            max = Math.max(max, set.size());
            list.add(s.substring(left, i + 1));
        }
        String res = "";

        for (String s1 : list) {
            if (s1.length() == max) {
                res = s1;
                break;
            }
        }

        return res;
    }


    /**
     * 方法二，要求返回最长的不重复的字符串，如果有多个，返回第一个
     * @param s
     * @return
     */
    public static String getMostLength2(String s) {
        if (s == null || s.length() <= 0) {
            return s;
        }
        Queue<Character> queue = new LinkedList<>();
        char[] array = s.toCharArray();
        int length = array.length;
        Map<Integer, String> map = new HashMap<>();
        int max = 0;
        for (int i = 0; i < length; i++) {
            //1. 如果存在相同的重复的元素，那么直接将这个元素从队里中排除
            while (queue.contains(array[i])) {
                queue.poll();
            }

            //2. 添加元素，通过上面的循环，可以保证添加元素时，queue中的内容永远都是不重复的
            queue.add(array[i]);
            max = Math.max(max, queue.size());

            if (!map.containsKey(max)) {
                StringBuilder sb = new StringBuilder();
                for (Character character : queue) {
                    sb.append(character);
                }
                map.put(max, sb.toString());
            }
        }
        return map.get(max);
    }
}
